package likou;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/08/21 08:57
 */
public class _337 {
    public int rob(TreeNode root) {
        int[] dp = dp(root);//一共两个元素，0：当前的节点选；1：当前的节点不选
        return Math.max(dp[0], dp[1]);
    }

    public int[] dp(TreeNode root) {
        if (root == null) return new int[]{0, 0};
        if (root.left == null && root.right == null) {
            return new int[]{root.val, 0};
        }
        int[] dp = new int[2];
        int[] left = dp(root.left);
        int[] right = dp(root.right);

        //要选当前节点，则子节点都不能选
        dp[0] = root.val + left[1] + right[1];
        //不选当前节点，子节点可选可不选，所以需要比较子节点选还是不选。
        dp[1] = Math.max(left[1],left[0]) + Math.max(right[1],right[0]);
        return dp;
    }
}
